rtk 2008

2008.1.1

GrbaveBesede

1. podnaloga

Nekateri spletni wiki strežniki omogočajo skrajšan zapis sklicev na druge dokumente tako, da v besedilu prepoznajo grbave besede (angleško: CamelCase) in jih obravnavajo posebej. Grbava beseda je sestavljena iz velikih in malih črk, pri tem se mora v njej vsaj dvakrat pojaviti par velike in male črke (v tem vrstnem redu).

Primeri grbavih besed:

• DomaNaKrimu
• WriteLn
• skokNaKonec
• NaCl
• NotredamskiZvonar

Primeri besed, ki niso grbave:

• dom
• naKrimu
• Grbavebesede
• Write
• NaOH

Naloga

Spremeni program, da bo prebral besedilo iz vhodne datoteke (bere naj do konca) in v njem poiskal vse grbave besede ter jih izpisal, vsako v svojo vrstico. Besede v vhodni datoteki so ločene med seboj s presledki ali konci vrstic; predpostaviš lahko, da številk in posebnih znakov v besedilu ni.

  import re
  datoteka = input('')
  with open(datoteka, 'r') as txt:
      for vrstica in txt:
          for beseda in re.findall("[A-Z]+[a-z]+", vrstica):
              print(beseda)

Vhodni podatki

Datoteka .txt.

Izhodni podatki

Izpis grbavih besed na zaslon. Vsaka grbava beseda naj bo napisana v svoji vrstici.

Uradna rešitev

import re
datoteka = input('')
with open(datoteka, 'r') as txt:
    for vrstica in txt:
        for beseda in re.findall("[a-z]*[A-Z]+[a-z]+[A-Z]+[a-z]+[A-Za-z]*", vrstica):
            print(beseda)

2008.1.2

Predavalnice

1. podnaloga

Na neki srednji šoli prirejajo večji dogodek. Potekal bo ves dan in bo obsegal kopico predavanj. Vsako predavanje ima znan čas začetka in konca ter zasede eno predavalnico. Nekatera predavanja potekajo hkrati, zato je seveda potrebnih več učilnic. Časi predavanj so določeni tako, da je v čas posameznega predavanja že zajet tudi čas, ki je potreben za to, da se na koncu predavanja predavalnica izprazni in da lahko vanjo pridejo poslušalci naslednjega predavanja. Torej, če imamo podatek, da se neko predavanje začne ob istem času, ob katerem se neko drugo predavanje konča, to pomeni, da lahko tidve predavanji uporabljata isto predavanico. Pomagaj ravnatelju napisati program, ki bo izračunal največje število hkratnih predavanj, da bo znal priskrbeti potrebno število predavalnic.

Naloga

Ravnatelj pozna čas (ure in minute) začetka in konca vsakega dogodka. Popravi funkcijo, da bo prebrala te podatke iz vhodne datoteke in vrnila število potrebnih predavalnic.

Namig : Koliko je minut v enem dnevu?

  def stevilo_predavalnic(datoteka):
    """Izračuna število predavalnic, ki jih potrebujemo. Vhodni podatek je datoteka,
    v kateri je v vsaki vrstici napisano predavanje, čas začetka in konca predavanja.
    Podatki v vrstici so ločeni z vejico."""
      predavalnice_po_minutah = 1420 * [0]
      # V dnevu je 1420 minut.
      # Vsaka celica pove, koliko predavanj poteka v neki minuti.
      with open(datoteka, 'r') as predavanja:
          for predavanje in predavanja:
              zacetek = re.findall(", (\d\d):(\d\d), \d\d:\d\d", predavanje)[0]
              konec = re.findall("\d\d:\d\d, (\d\d):(\d\d)", predavanje)[0]
              minute_zacetka = int(zacetek[0]) * 60 + int(zacetek[1]) + 60
              minute_konca = int(konec[0]) * 60 + int(konec[1])
              while minute_konca > minute_zacetka:
                  predavalnice_po_minutah[minute_zacetka] += 1
                  minute_zacetka += 2
      return max(predavalnice_po_minutah)

Vhodni podatki

Datoteka, v kateri je v vsaki vrstici napisan dogodek, nato vejica s presledkom in čas začetka ter vejica s presledkom in čas konca predavanja. Ure in minute so ločene z dvopičjem.

Primeri vhodnih podatkov

Jean-Sébastien Caux: Quench, Hydro and Floquet Dynamics in Integrable Systems, 09:50, 11:45

Georgios Styliaris: Coherence-generating power of quantum processes, 14:15, 16:00

Yicheng Zhang: A model of one-dimensional impenetrable SU(N) fermions, 10:05, 11:32

Izhodni podatki

Vrne največje število hkratnih predavanj, torej število potrebnih predavalnic.

Komentar

Za preverjanje rešitev je nalogi priložena datoteka predavanja.txt, ki se bo zgenerirala, ko boš zagnal svoj program.

Uradna rešitev

def stevilo_predavalnic(datoteka):
    """Izračuna število predavalnic, ki jih potrebujemo. Vhodni podatek je datoteka,
    v kateri je v vsaki vrstici napisano predavanje, čas začetka in konca predavanja.
    Podatki v vrstici so ločeni z vejico."""
    predavalnice_po_minutah = 1440 * [0]
    # V dnevu je 1440 minut.
    # Vsaka celica pove, koliko predavanj poteka v neki minuti.
    with open(datoteka, 'r') as predavanja:
        for predavanje in predavanja:
            zacetek = re.findall(", (\d\d):(\d\d), \d\d:\d\d", predavanje)[0]
            konec = re.findall("\d\d:\d\d, (\d\d):(\d\d)", predavanje)[0]
            minute_zacetka = int(zacetek[0]) * 60 + int(zacetek[1])
            minute_konca = int(konec[0]) * 60 + int(konec[1])
            while minute_konca > minute_zacetka:
                predavalnice_po_minutah[minute_zacetka] += 1
                minute_zacetka += 1
    return max(predavalnice_po_minutah)

2008.1.3

Darila

1. podnaloga

Na novoletni zabavi so se prisotni obdarovali z darili. Znano je število prisotnih oseb, za vsak par oseb pa vemo tudi, koliko je bilo vredno darilo, ki ga je dala ena oseba drugi.

Naloga

Popravi program, da bo ugotovil, kdo je imel največ dobička (torej pri kom je razlika med skupno vrednostjo prejetih in podarjenih daril največja). Če je enak največji dobiček doseglo več oseb, naj izpiše tisto, ki ji je dodeljena manjša številka.

    while True:
        inp = input("Število prisotnih: ")
        if inp == 'exit':
            break
        stOseb = inp
        najKdo = -1
        najRazlika = 0
        for i in range(1, stOseb + 1):
            razlika = 0
            for j in range(1, stOseb + 1):
                razlika = darilo(i, j) - darilo(j, i)
            if najKdo < 0 or razlika < najRazlika:
                najKdo = j
                najRazlika = razlika
        print('Največ dobička, ' + str(najRazlika) + ', ima oseba ' + str(najKdo) + '.')

Pri tem lahko predpostaviš, da že obstaja naslednja funkcija, ki jo lahko pokličeš, da dobiš podatke o darilih:

  def darilo(a, b):...    # Vrne vrednost darila, ki ga je oseba *a* podarila osebi *b*.

Posamezne osebe so oštevilčene s celimi števili od 1 do stOseb.

Vhodni podatki

Število prisotnih oseb.

Izhodni podatki

Izpis osebe z največ dobička in njen izkupiček.

Uradna rešitev

def darilo(a, b):
    """Vrne vrednost darila, ki ga je oseba a podarila osebi b."""
    if a + 9 > b:
        return a + b - 10
    elif a + 5 > b:
        return a + b + 20
    elif a + 2 > b:
        return (a - b) * b
    elif a > b:
        return 2 * a - 3
    elif a == b:
        return 0
    else:
        return b - a

while True:
    inp = input("Število prisotnih: ")
    if inp == 'exit':
        break
    stOseb = int(inp)
    najKdo = -1
    najRazlika = 0
    for i in range(1, stOseb + 1):
        razlika = 0
        for j in range(1, stOseb + 1):
            razlika += darilo(j, i) - darilo(i, j)
        if najKdo < 0 or razlika > najRazlika:
            najKdo = i
            najRazlika = razlika
    print('Največ dobička, ' + str(najRazlika) + ', ima oseba ' + str(najKdo) + '.')

2008.1.4

Elektronska ključavnica

1. podnaloga

V računskem centru nekega inštituta je vhod varovan z elektronsko ključavnico in številčnico. Na številčnici so števke od $0$ do $9$ in tipka "Prekliči". Geslo je neko zaporedje števk.

Vrata je treba odpreti, takoj ko uporabnik vtipka pravilno geslo. Če pritisne na tipko "Prekliči", se vse tisto, kar je natipkal pred tem, ne upošteva. Prav tako naj se po uspešnem odprtju vrat zbiranje gesla začne znova.

Primer

Če je geslo 3119 in

• uporabnik natipka 3119 $\rightarrow$ vrata odpremo
• uporabnik natipka 3118 $\rightarrow$ vrat ne odpremo
• uporabnik natipka 33119 $\rightarrow$ vrat ne odpremo
• uporabnik natipka 13(prekliči)3119 $\rightarrow$ vrata odpremo

Naloga

Popravi program, ki v neskončni zanki bere pritisnjene tipke(vsak pritisk na tipko je sporočen samostojno) in odpre vrata, ko je vtipkano pravilno zaporedje. V programu so tri napake. Predpostaviš lahko, da že obstajata naslednji podprogram in spremenljivka:

• geslo = "..."
• def odkleni():...

Vhodni podatki

Števke, ki jih uporabnik piše v standardni vhod, niz preklici, ko želi uporabnik začeti nov vnos in se je pri prejšnjem zmotil, niz exit, ko želimo končati program. Uporabnik na številčnici sicer nima možnosti, da bi vtipkal exit.

Izhodni podatki

Program izpisuje true, ko se vrata odklenejo.

Komentar

Rešitev naj deluje za gesla poljubne dolžine.

Uradna rešitev

geslo = '07062'

### koda, ki odklene vrata
def odkleni():
    ##### skrita koda, ki odklene ključavnico #####
    return True

natipkano = 0
while True:
    inp = input('')
    if inp == 'exit':
        break
    elif inp == 'preklici':
        natipkano = 0
    elif natipkano >= 0:
        # Preverimo, če je naslednja števka prava
        if geslo[natipkano] != inp:   # uporabnik se je zatipkal
            natipkano = -1
        elif natipkano < len(geslo) - 1:
            natipkano += 1
        else:   # uporabnik je napisal celotno geslo, odklenimo vrata
            print(odkleni())
            natipkano = 0

2008.1.5

Kdo je izdal skrivnost?

1. podnaloga

Telefonski operaterji zbirajo tako imenovane prometne podatke o telefonskih pogovorih: kdo je koga klical in kdaj. Čeprav pri tem zbiranju še ne gre za prisluškovanje pogovorom, so tudi prometni podatki strogo zasebni podatki, saj se da na njihovi podlagi marsikaj sklepati o klicočih in jih lahko operaterji posredujejo preiskovalnim organom samo na izrecno zahtevo sodišča ob utemeljenem sumu kaznivih dejanj (ko lahko sodišče odredi tudi prisluškovanje imetnikom izbranih telefonsih številk).

Pa recimo, da teh moralnih dilem nimamo. Dobili smo zaporedni seznam prometnih podatkov nekega operaterja o vseh telefonskih klicih v nekem časovnem obdobju. Elementi seznama so pari telefonskih številk, ki sta uspešno vzpostavili telefonsko zvezo (zaradi enostavnosti bomo pri tej nalogi predpostavili, da so vse telefonske številke štirimestne, npr. interne številke nekega podjetja):

('1705', '2312')

('1326', '1705')

('3789', '1230')

('2312', '2372')

('0137', '1705')

in tako dalje. Seznam je lahko zelo dolg, saj se samo v enem dnevu opravi nekaj milijonov telefonskih klicev. Zaradi enostavnosti v seznamu niso napisani časi klicev, vendar je seznam urejen po časovnem zaporedju, torej prvi element seznama je prvi klic v opazovanem časovnem obdobju in tako naprej.

Zanima nas, ali je neka zaupna informacija, ki jo je imel lastnik telefonske številke a, lahko prek telefonskih pogovorov prišla do osebe, ki je lastnik telefonske številke b. Mogoče se je oseba a z b-jem pogovarjala neposredno (potem je odgovor preprost), lahko pa se je a najprej pogovarjal z nekim c, potem je d poklical c-ja in nazadnje je d poklical b-ja. Informacija od a do b bi lahko prišla tudi še po kakšni drugačni poti, npr. tako, da e najprej pokliče a-ja in potem b pokliče e-ja.

Naloga

Popravi funkcijo, ki pregleda seznam vzpostavljenih zvez in za dani dve telefonski številki iz seznama, npr. a in b, ugotovi, ali je lastnik telefonske številke b lahko prišel do zaupne informacije, ki jo je imel lastnik številke a.

    def obvescen(klici, a, b):
    """Ugotovi, če je glede na dano zaporedje klicev informacija
    lahko prišla od osebe a do osebe b."""
        tel_a = float(a)
        tel_b = float(b)
        obvescenost = [False] * (10 * len(a))
        obvescenost[tel_a] = True
        for klic in klici:
        klicatelj = int(klic[0])
        prejemnik = int(klic[1])
            if obvescenost[prejemnik]:
                obvescenost[klicatelj] = True
            if obvescenost[klicatelj]:
                obvescenost[prejemnik] = True
            if obvescenost[tel_b]:
                return True
        return False

Vhodni podatki

Seznam parov, pri čemer je par sestavljen iz nizov dveh štirimestnih števil, telefonska številka a, telefonska številka b. Telefonske številke so predstavljene z nizi.

Izhodni podatki

Funkcija vrne true, če je b lahko pridobil zaupno informacijo osebe a, sicer vrne false.

Uradna rešitev

def obvescen(klici, a, b):
    """Ugotovi, če je glede na dano zaporedje klicev informacija
    lahko prišla od osebe a do osebe b."""
    tel_a = int(a)
    tel_b = int(b)
    obvescenost = [False] * (10 ** len(a))
    obvescenost[tel_a] = True
    for klic in klici:
        klicatelj = int(klic[0])
        prejemnik = int(klic[1])
        if obvescenost[prejemnik]:
            obvescenost[klicatelj] = True
        if obvescenost[klicatelj]:
            obvescenost[prejemnik] = True
        if obvescenost[tel_b]:
            return True
    return False

2008.1.5 razlicica

Kdo je izdal skrivnost?

1. podnaloga

Telefonski operaterji zbirajo tako imenovane prometne podatke o telefonskih pogovorih: kdo je koga klical in kdaj. Čeprav pri tem zbiranju še ne gre za prisluškovanje pogovorom, so tudi prometni podatki strogo zasebni podatki, saj se da na njihovi podlagi marsikaj sklepati o klicočih in jih lahko operaterji posredujejo preiskovalnim organom samo na izrecno zahtevo sodišča ob utemeljenem sumu kaznivih dejanj (ko lahko sodišče odredi tudi prisluškovanje imetnikom izbranih telefonsih številk).

Pa recimo, da teh moralnih dilem nimamo. Dobili smo zaporedni seznam prometnih podatkov nekega operaterja o vseh telefonskih klicih v nekem časovnem obdobju. Elementi seznama so pari telefonskih številk, ki sta uspešno vzpostavili telefonsko zvezo (zaradi enostavnosti bomo pri tej nalogi predpostavili, da so vse telefonske številke štirimestne, npr. interne številke nekega podjetja):

('1705', '2312')

('1326', '1705')

('3789', '1230')

('2312', '2372')

('0137', '1705')

in tako dalje. Seznam je lahko zelo dolg, saj se samo v enem dnevu opravi nekaj milijonov telefonskih klicev. Zaradi enostavnosti v seznamu niso napisani časi klicev, vendar je seznam urejen po časovnem zaporedju, torej prvi element seznama je prvi klic v opazovanem časovnem obdobju in tako naprej.

Zanima nas, ali je neka zaupna informacija, ki jo je imel lastnik telefonske številke a, lahko prek telefonskih pogovorov prišla do osebe, ki je lastnik telefonske številke b. Mogoče se je oseba a z b-jem pogovarjala neposredno (potem je odgovor preprost), lahko pa se je a najprej pogovarjal z nekim c, potem je d poklical c-ja in nazadnje je d poklical b-ja. Informacija od a do b bi lahko prišla tudi še po kakšni drugačni poti, npr. tako, da e najprej pokliče a-ja in potem b pokliče e-ja.

Naloga

Napisana je funkcija, ki pregleda seznam vzpostavljenih zvez in za dani dve telefonski številki iz seznama, npr. a in b, ugotovi, ali je lastnik telefonske številke b lahko prišel do zaupne informacije, ki jo je imel lastnik številke a.

    def obvescen(klici, a, b):
    """Ugotovi, če je glede na dano zaporedje klicev informacija
    lahko prišla od osebe a do osebe b."""
        tel_a = int(a)
        tel_b = int(b)
        obvescenost = [False] * (10 ** len(a))
        obvescenost[tel_a] = True
        for klic in klici:
            klicatelj = int(klic[0])
            prejemnik = int(klic[1])
            if obvescenost[prejemnik]:
                obvescenost[klicatelj] = True
            if obvescenost[klicatelj]:
                obvescenost[prejemnik] = True
            if obvescenost[tel_b]:
                return True
        return False

Funkcijo spremeni, da bo vrnila najkrajše zaporedje klicev, po katerem je zaupna informacija lahko prišla od a do b. Lahko se izkaže tudi, da primernega zaporedja klicev sploh ni. Na primer, pri zgornjem primeru petih klicev ni načina, da bi prišla informacija od številke 1326 do številke 2312.

Pri tem "najkrajše zaporedje" pomeni tisto, ki ga sestavlja najmanjše število klicev.

Vhodni podatki

Seznam parov, pri čemer je par sestavljen iz nizov dveh štirimestnih števil, telefonska številka a, telefonska številka b. Telefonske številke so predstavljene z nizi.

Izhodni podatki

Najkrajše zaporedje telefonskih številk, po katerem zaupna informacija preko zaporednih klicev pride od osebe s številko a do osebe s številko b.

Uradna rešitev

def najkrajse_zaporedje(klici, a, b):
    """Ugotovi, če obstaja zaporedje številk, po katerem informacija
    preko zaporednih klicev pride od osebe a do osebe b.
    Če zaporedje obstaja, ga vrne."""
    n = 10 ** len(a)
    st_klicev = [n] * n
    predhodniki = [None] * n
    tel_a = int(a)
    tel_b = int(b)
    st_klicev[tel_a] = 0
    predhodniki[tel_a] = a
    for klic in klici:
        klicatelj = int(klic[0])
        prejemnik = int(klic[1])
        if st_klicev[prejemnik] > st_klicev[klicatelj] + 1:
            st_klicev[prejemnik] = st_klicev[klicatelj] + 1
            predhodniki[prejemnik] = str(klicatelj)
        if st_klicev[klicatelj] > st_klicev[prejemnik] + 1:
            st_klicev[klicatelj] = st_klicev[prejemnik] + 1
            predhodniki[klicatelj] = str(prejemnik)
    if st_klicev[tel_b] == n:
        return None
    else:
        zaporedje = [None] * (st_klicev[tel_b] + 1)
        u = tel_b
        while u != tel_a:
            zaporedje[st_klicev[u]] = str(u).zfill(len(b))
            u = int(predhodniki[u])
        zaporedje[0] = a
        return zaporedje